/**
 * 给定一个数组A，再给定一个swap数组
 * swap数组包含若干个(x, y)，表示Ax与Ay能够交换
 * 要求求下述式子的最大值：
 *   SIGMA{A[0,2,4,...]} - SIGMA{A[1,3,5,...]}
 * 
 * 如果(x,y)(y,z)同时存在，则本质上(x,z)也是可以交换的
 * 且可以实现xyz的任意排列
 * 因此首先将所有连通的位置归类，对每一类
 * 将元素值排序，然后将尽可能大的元素赋给偶数下标，小元素赋给奇数下标即可
 */

struct UFSet{ // 并查集

vector<int> father;

void init(int n){father.assign(n+1, 0);for(int i=1;i<=n;++i)father[i]=i;}

int find(int x){return father[x]==x?x:father[x]=find(father[x]);}

void unite(int x, int y){father[find(y)]=find(x);}

};


class Solution {
using pii = pair<int, int>;
public:
    long long maxAlternatingSum(vector<int>& nums, vector<vector<int>>& swaps) {
        int N = nums.size();
        UFSet U;
        U.init(N);
        for(const auto & v : swaps){
            U.unite(v[0], v[1]);
        }

        map<int, pair<vector<int>,pii>> Map;
        for(int i=0;i<N;++i){
            auto f = U.find(i);
            Map[f].first.push_back(nums[i]);
        }

        for(auto & p : Map){
            sort(p.second.first.begin(), p.second.first.end());
            p.second.second = {0, p.second.first.size() - 1};
        }

        long long ans = 0;
        for(int i=0;i<N;++i){
            auto f = U.find(i);
            auto it = Map.find(f);
            assert(it != Map.end());

            const auto & v = it->second.first;
            auto & left = it->second.second.first;
            auto & right = it->second.second.second;

            if(i % 2 == 0){
                ans += v[right--];
            }else{
                ans -= v[left++];
            }
        }
        return ans;
    }
};